| class A_SELECT{ETP,ATP< $ARR{ETP}} |
|---|
| **** | Basic algorithms for order statistics Most of these algorithms MODIFY THE ORIGINAL ARRAY! |
| COMPARE{_} |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| median_modifying(a: ATP): ETP |
|---|
| **** | The median of the elements contained in 'a' according to the ordering relation `elt_lt'. Permutes the elements of 'a'. Void if self is empty |
| select_modifying(a: ATP,i:INT,lp,up: INT): ETP |
|---|
| **** | Modifies "a" Move the elements of a so that the element with index `i' is not `elt_lt' any element with lower indices and no element with a larger index is `elt_lt' it. Use the subarray in the range l,u Return the "ith" element in the rearranged array |
| select_modifying(a:ATP,lt:ROUT{ETP,ETP}:BOOL, i:INT,lp,up: INT):ETP |
|---|
| **** | Modifies 'a' Move the elements of 'a' so that the element with index `i' is not `lt' any element with lower indices and no element with a larger index is `lt' it. |
| check_index(a: ATP,i: INT,l,u: INT): BOOL |
|---|
| swap(a: ATP,order: ARRAY{INT},i,j: INT) |
|---|
| swap(a: ATP,i,j: INT) |
|---|